package org.lql.algo.codecrush.week008;

import java.util.Arrays;

/**
 * @author: liangqinglong
 * @date: 2025-08-19 00:04
 * @description: 1122. 数组的相对排序 <a href="https://leetcode.cn/problems/relative-sort-array/description/">...</a>
 **/
public class RelativeSortArray {

	// arr1 = [2,3,1,3,2,4,6,7,9,2,19],

	// arr2 = [2,1,4,3,9,6]

	// [2,2,2,1,4,3,3,9,6,7,19]

	// 1 <= arr1.length, arr2.length <= 1000

	public int[] relativeSortArray(int[] arr1, int[] arr2) {
		int[] count = new int[1001]; // 创建一个长度为1001的数组，用于记录arr1中每个数字出现的次数
		for (int num : arr1) {
			count[num]++; // 统计arr1中每个数字出现的次数
		}
		int index = 0;
		for (int num : arr2) {
			while (count[num] > 0) {
				arr1[index++] = num; // 将arr2中的数字按照出现的顺序放入arr1中
				count[num]--; // 减去arr1中该数字出现的次数
			}
		}
		for (int i = 0; i < count.length; i++) {
			while (count[i] > 0) {
				arr1[index++] = i; // 将arr1中剩余的数字按照出现的顺序放入arr1中
				count[i]--; // 减去arr1中该数字出现的次数
			}
		}
		return arr1;
	}

	public static void main(String[] args) {
		int[] arr1 = new int[]{2, 3, 1, 3, 2, 4, 6, 7, 9, 2, 19};
		int[] arr2 = new int[]{2, 1, 4, 3, 9, 6};
		RelativeSortArray relativeSortArray = new RelativeSortArray();
		int[] result = relativeSortArray.relativeSortArray(arr1, arr2);
		System.out.println(Arrays.toString(result));
	}
}
